#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
private:
    int getKey(const vector<int>& cells) {
        int res = 0;
        for (int i = 0; i < cells.size(); ++i)
            res = res * 10 + cells[i];
        return res;
    }

    vector<int> getVec(int key) {
        vector<int> res(8, 0);
        for (int i = res.size()-1; i >= 0; --i) {
            res[i] = key % 10;
            key /= 10;
            if (key == 0) break;
        }
        return res;
    }

public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        unordered_map<int, int>map;
        vector<int> visited;
        vector<int> res = cells;
        for (int i = 0; i < N; ++i) {
            int key = getKey(cells);
            if (map.find(key) != map.end()) {
                int cycle = i - map[key];
                i = (N - i) % cycle + map[key];
                return getVec(visited[i]);
            }
            visited.push_back(key);
            map[key] = i;

            for (int j = 1; j < cells.size() - 1; ++j) {
                res[j] = cells[j - 1] == cells[j + 1];
            }
            res[0] = res[res.size() - 1] = 0;
            swap(res, cells);
        }
        return cells;
    }
};